# rbNarcissus written by Paul Sowden
#
#   A ruby port of the Mozilla Narcissus Javascript parser
#   Narcissus - http://lxr.mozilla.org/mozilla/source/js/narcissus/jsparse.js
#   rbNarcissus - http://idontsmoke.co.uk/2005/rbnarcissus/
# 
#     Feel free to download, use and abuse the script. Because it's derived from the
#     original Narcissus source code the tri-licence remains and you are able to
#     choose from the MPL 1.1, GPL 2.0 and LGPL 2.1 licences, you lucky people.
# 
# modifications by Duncan Beevers, Kongregate 2007
#
module RbNarcissus
  TOKENS = [
  	# End of source.
  	"END",

  	# Operators and punctuators.  Some pair-wise order matters, e.g. (+, -)
  	# and (UNARY_PLUS, UNARY_MINUS).
  	"\n", ";",
  	",",
  	"=",
  	"?", ":", "CONDITIONAL",
  	"||",
  	"&&",
  	"|",
  	"^",
  	"&",
  	"==", "!=", "===", "!==",
  	"<", "<=", ">=", ">",
  	"<<", ">>", ">>>",
  	"+", "-",
  	"*", "/", "%",
  	"!", "~", "UNARY_PLUS", "UNARY_MINUS",
  	"++", "--",
  	".",
  	"[", "]",
  	"{", "}",
  	"(", ")",

  	# Nonterminal tree node type codes.
  	"SCRIPT", "BLOCK", "LABEL", "FOR_IN", "CALL", "NEW_WITH_ARGS", "INDEX",
  	"ARRAY_INIT", "OBJECT_INIT", "PROPERTY_INIT", "GETTER", "SETTER",
  	"GROUP", "LIST",

  	# Terminals.
  	"IDENTIFIER", "NUMBER", "STRING", "REGEXP",

  	# Keywords.
  	"break",
  	"case", "catch", "const", "continue",
  	"debugger", "default", "delete", "do",
  	"else", "enum",
  	"false", "finally", "for", "function",
  	"if", "in", "instanceof",
  	"new", "null",
  	"return",
  	"switch",
  	"this", "throw", "true", "try", "typeof",
  	"var", "void",
  	"while", "with",
  ]

  # A numeric lookup hash to Javascript Ops.  All entries from TOKENS are recognized.
  NODE = Hash[*TOKENS.inject([]){ |a,token| [ token, (a.size / 2), a ].flatten}]

  # Operator and punctuator mapping from token to tree node type name.
  OP_TYPE_NAMES = {
  	"\n"  => "NEWLINE",
  	';'   => "SEMICOLON",
  	','   => "COMMA",
  	'?'   => "HOOK",
  	':'   => "COLON",
  	'||'  => "OR",
  	'&&'  => "AND",
  	'|'   => "BITWISE_OR",
  	'^'   => "BITWISE_XOR",
  	'&'   => "BITWISE_AND",
  	'===' => "STRICT_EQ",
  	'=='  => "EQ",
  	'='   => "ASSIGN",
  	'!==' => "STRICT_NE",
  	'!='  => "NE",
  	'<<'  => "LSH",
  	'<='  => "LE",
  	'<'   => "LT",
  	'>>>' => "URSH",
  	'>>'  => "RSH",
  	'>='  => "GE",
  	'>'   => "GT",
  	'++'  => "INCREMENT",
  	'--'  => "DECREMENT",
  	'+'   => "PLUS",
  	'-'   => "MINUS",
  	'*'   => "MUL",
  	'/'   => "DIV",
  	'%'   => "MOD",
  	'!'   => "NOT",
  	'~'   => "BITWISE_NOT",
  	'.'   => "DOT",
  	'['   => "LEFT_BRACKET",
  	']'   => "RIGHT_BRACKET",
  	'{'   => "LEFT_CURLY",
  	'}'   => "RIGHT_CURLY",
  	'('   => "LEFT_PAREN",
  	')'   => "RIGHT_PAREN"
  }

  class JavascriptParser
    attr_accessor :parse_substitutes

    # Hash of keyword identifier to tokens index.
    $keywords = {}

    # Define const END, etc., based on the token names.  Also map name to index.
    $consts = {}

    TOKENS.length.times do |i|
    	t = TOKENS[i]
    	if /\A[a-z]/ =~ t
    		$consts[t.upcase] = i
    		$keywords[t] = i
    	elsif /\A\W/ =~ t
    		$consts[OP_TYPE_NAMES[t]] = i
    	else
    		$consts[t] = i
    	end
    end

    # Map assignment operators to their indexes in the TOKENS array.
    $assignOps = ['|', '^', '&', '<<', '>>', '>>>', '+', '-', '*', '/', '%']
    $assignOpsHash = {}

    $assignOps.length.times do |i|
    	t = $assignOps[i]
    	$assignOpsHash[t] = $consts[OP_TYPE_NAMES[t]]
    end

    $opPrecedence = {
    	"SEMICOLON" => 0,
    	"COMMA" => 1,
    	"ASSIGN" => 2,
    	"HOOK" => 3, "COLON" => 3, "CONDITIONAL" => 3,
    	"OR" => 4,
    	"AND" => 5,
    	"BITWISE_OR" => 6,
    	"BITWISE_XOR" => 7,
    	"BITWISE_AND" => 8,
    	"EQ" => 9, "NE" => 9, "STRICT_EQ" => 9, "STRICT_NE" => 9,
    	"LT" => 10, "LE" => 10, "GE" => 10, "GT" => 10, "IN" => 10, "INSTANCEOF" => 10,
    	"LSH" => 11, "RSH" => 11, "URSH" => 11,
    	"PLUS" => 12, "MINUS" => 12,
    	"MUL" => 13, "DIV" => 13, "MOD" => 13,
    	"DELETE" => 14, "VOID" => 14, "TYPEOF" => 14, # PRE_INCREMENT: 14, PRE_DECREMENT: 14,
    	"NOT" => 14, "BITWISE_NOT" => 14, "UNARY_PLUS" => 14, "UNARY_MINUS" => 14,
    	"INCREMENT" => 15, "DECREMENT" => 15, # postfix
    	"NEW" => 16,
    	"DOT" => 17
    }

    # Map operator type code to precedence.
    $opPrecedence.keys.each do |i|
    	$opPrecedence[$consts[i]] = $opPrecedence[i]
    end

    $opArity = {
    	"COMMA" => -2,
    	"ASSIGN" => 2,
    	"CONDITIONAL" => 3,
    	"OR" => 2,
    	"AND" => 2,
    	"BITWISE_OR" => 2,
    	"BITWISE_XOR" => 2,
    	"BITWISE_AND" => 2,
    	"EQ" => 2, "NE" => 2, "STRICT_EQ" => 2, "STRICT_NE" => 2,
    	"LT" => 2, "LE" => 2, "GE" => 2, "GT" => 2, "IN" => 2, "INSTANCEOF" => 2,
    	"LSH" => 2, "RSH" => 2, "URSH" => 2,
    	"PLUS" => 2, "MINUS" => 2,
    	"MUL" => 2, "DIV" => 2, "MOD" => 2,
    	"DELETE" => 1, "VOID" => 1, "TYPEOF" => 1, # PRE_INCREMENT: 1, PRE_DECREMENT: 1,
    	"NOT" => 1, "BITWISE_NOT" => 1, "UNARY_PLUS" => 1, "UNARY_MINUS" => 1,
    	"INCREMENT" => 1, "DECREMENT" => 1,   # postfix
    	"NEW" => 1, "NEW_WITH_ARGS" => 2, "DOT" => 2, "INDEX" => 2, "CALL" => 2,
    	"ARRAY_INIT" => 1, "OBJECT_INIT" => 1, "GROUP" => 1
    }

    # Map operator type code to arity.
    $opArity.keys.each do |i|
    	$opArity[$consts[i]] = $opArity[i]
    end


    # NB: superstring tokens (e.g., ++) must come before their substring token
    # counterparts (+ in the example), so that the $opRegExp regular expression
    # synthesized from this list makes the longest possible match.
    $ops = [';', ',', '?', ':', '||', '&&', '|', '^', '&', '===', '==', 
    	'=', '!==', '!=', '<<', '<=', '<', '>>>', '>>', '>=', '>', '++', '--',
    	'+', '-', '*', '/', '%', '!', '~', '.', '[', ']', '{', '}', '(', ')']

    # Build a regexp that recognizes operators and punctuators (except newline).
    $opRegExpSrc = "\\A"
    $ops.length.times do |i|
    	$opRegExpSrc += "|\\A" if $opRegExpSrc != "\\A"
    	$opRegExpSrc += $ops[i].gsub(/([?|^&(){}\[\]+\-*\/\.])/) {|s| "\\" + s}
    end
    $opRegExp = Regexp.new($opRegExpSrc, Regexp::MULTILINE)


    # A regexp to match floating point literals (but not integer literals).
    $fpRegExp = Regexp.new("\\A\\d+\\.\\d*(?:[eE][-+]?\\d+)?|\\A\\d+(?:\\.\\d*)?[eE][-+]?\\d+|\\A\\.\\d+(?:[eE][-+]?\\d+)?", Regexp::MULTILINE)


    class Tokenizer
      attr_accessor :parse_substitutes

    	attr_accessor :cursor, :source, :tokens, :tokenIndex, :lookahead
    	attr_accessor :scanNewlines, :scanOperand, :filename, :lineno

    	def initialize (source, filename, line)
    		@cursor = 0
    		@source = source.to_s
    		@tokens = []
    		@tokenIndex = 0
    		@lookahead = 0
    		@scanNewlines = false
    		@scanOperand = true
    		@filename = filename or ""
    		@lineno = line or 1
    	end

    	def input
    		return @source.slice(@cursor, @source.length - @cursor)
    	end

    	def done
    		return self.peek == $consts["END"];
    	end

    	def token
    		return @tokens[@tokenIndex];
    	end
	
    	def match (tt)
    		got = self.get
    		#puts got
    		#puts tt
    		return got == tt || self.unget
    	end
	
    	def mustMatch (tt)
    		raise SyntaxError, JavascriptParser::format_error_message("Missing " + TOKENS[tt].downcase, self) unless self.match(tt)
    		return self.token
    	end

    	def peek
    		if @lookahead > 0
    			#tt = @tokens[(@tokenIndex + @lookahead)].type
    			tt = @tokens[(@tokenIndex + @lookahead) & 3].type
    		else
    			tt = self.get
    			self.unget
    		end
    		return tt
    	end
	
    	def peekOnSameLine
    		@scanNewlines = true;
    		tt = self.peek
    		@scanNewlines = false;
    		return tt
    	end

    	def get
    		while @lookahead > 0
    			@lookahead -= 1
    			@tokenIndex = (@tokenIndex + 1) & 3
    			token = @tokens[@tokenIndex]
    			return token.type if token.type != $consts["NEWLINE"] || @scanNewlines
    		end

    		while true
    			input = self.input

    			if @scanNewlines
    				match = /\A[ \t]+/.match(input)
    			else
    				match = /\A\s+/.match(input)
    			end
			
    			if match
    				spaces = match[0]
    				@cursor += spaces.length
    				@lineno += spaces.count("\n")
    				input = self.input
    			end
			
    			match = /\A\/(?:\*(?:.)*?\*\/|\/[^\n]*)/m.match(input)
    			break unless match
    			comment = match[0]
    			@cursor += comment.length
    			@lineno += comment.count("\n")
    		end

        # puts input
		
    		@tokenIndex = (@tokenIndex + 1) & 3
    		token = @tokens[@tokenIndex]
    		(@tokens[@tokenIndex] = token = Token.new) unless token
    		if input.length == 0
    			#puts "end!!!"
    			return (token.type = $consts["END"])
    		end

    		cursor_advance = 0

        # First attempt to catch parse_substitutes
        token.capture = false
    		if self.parse_substitutes && (match = /^%STRING/.match(input))
    		  token.type = $consts['STRING']
          token.value = nil
          token.capture = true
        elsif self.parse_substitutes && (match = /^%NUMBER/.match(input))
          token.type = $consts['NUMBER']
          token.value = nil
          token.capture = true
        # elsif self.parse_substitutes && (match = /^%OBJECT/.match(input))
        #   token.type = $consts['OBJECT_INIT']
        #   token.capture = true
    		elsif (match = $fpRegExp.match(input))
    			token.type = $consts["NUMBER"]
    			token.value = match[0].to_f
    		elsif (match = /\A0[xX][\da-fA-F]+|\A0[0-7]*|\A\d+/.match(input))
    			token.type = $consts["NUMBER"]
    			token.value = match[0].to_i
    		elsif (match = /\A(\w|\$)+/.match(input))
    			id = match[0]
    			token.type = $keywords[id] || $consts["IDENTIFIER"]
    			case token.type
    			when $consts["NULL"] then token.value = nil
    			when $consts["TRUE"] then token.value = true
    			when $consts["FALSE"] then token.value = false
  			  else
      			token.value = id
    			end
    		elsif (match = /\A"(?:(\\.)|[^"])*"|\A'(?:(\\.)|[^'])*'/.match(input))
    			token.type = $consts["STRING"]
			token.value = match[0].to_s.slice(1..-2)
    		elsif @scanOperand and (match = /\A\/((?:\\.|[^\/])+)\/([gim]*)/.match(input))
    			token.type = $consts["REGEXP"]
    			token.value = Regexp.new(Regexp.escape(match[1]), Regexp.escape(match[2]))
    		elsif (match = $opRegExp.match(input))
    			op = match[0]
    			if $assignOpsHash[op] && input[op.length, 1] == '='
    				token.type = $consts["ASSIGN"]
    				token.assignOp = $consts[OP_TYPE_NAMES[op]]
    				cursor_advance = 1 # length of '='
    			else
    				#puts $consts[OP_TYPE_NAMES[op]].to_s + " " + OP_TYPE_NAMES[op] + " " + op
    				token.type = $consts[OP_TYPE_NAMES[op]]
    				if @scanOperand and (token.type == $consts["PLUS"] || token.type == $consts["MINUS"])
    					token.type += $consts["UNARY_PLUS"] - $consts["PLUS"]
    				end
    				token.assignOp = nil
    			end
    			token.value = op

    		else
    			raise SyntaxError, JavascriptParser::format_error_message("Illegal token", self)
    		end

    		token.start = @cursor
    		@cursor += match[0].length + cursor_advance
    		token.end = @cursor
    		token.lineno = @lineno
    		return token.type
    	end

    	def unget
    		#puts "start: lookahead: " + @lookahead.to_s + " tokenIndex: " + @tokenIndex.to_s
    		@lookahead += 1
    		raise SyntaxError, JavascriptParser::format_error_message("PANIC: too much lookahead!", self) if @lookahead == 4
    		@tokenIndex = (@tokenIndex - 1) & 3
    		#puts "end:   lookahead: " + @lookahead.to_s + " tokenIndex: " + @tokenIndex.to_s
    		return nil
    	end

    end

    class SyntaxError < StandardError
    end


    class Token
    	attr_accessor :type, :value, :start, :end, :lineno, :assignOp

    	attr_accessor :capture
    end


    class CompilerContext
    	attr_accessor :inFunction, :stmtStack, :funDecls, :varDecls
    	attr_accessor :bracketLevel, :curlyLevel, :parenLevel, :hookLevel
    	attr_accessor :ecmaStrictMode, :inForLoopInit

    	def initialize (inFunction)
    		@inFunction = inFunction
    		@stmtStack = []
    		@funDecls = []
    		@varDecls = []
		
    		@bracketLevel = @curlyLevel = @parenLevel = @hookLevel = 0
    		@ecmaStrictMode = @inForLoopInit = false
    	end
    end


    class Node < Array
      # type provides the numeric type_code of this node.  Use Node#node_type for the string representation
      # lineno is the line number of the source file on which the node begins.
      # (?) is start the offset into the line of javascript to the beginning of this node?
      # (?) is end the offset into the line of javascript to the end of this node?
      NODE_METADATA_FIELDS = [
        :type, :lineno, :start, :end,
        :tokenizer, :initializer
      ]
      NESTABLE_NODE_FIELDS = [
        :body, :statement, :expression, :value, :thenPart, :elsePart, :condition, :funDecls, :varDecls, :setup
      ]

      UNNESTABLE_NODE_FIELDS = [
        :value,
        :name, :params, :funDecls, :varDecls, :functionForm,
        :assignOp, :condition, :thenPart, :elsePart,
        :readOnly, :isLoop, :setup, :postfix, :update, :exception,
        :object, :iterator, :varDecl, :label, :target, :tryBlock,
        :catchClauses, :varName, :guard, :block, :discriminant, :cases,
        :defaultIndex, :caseLabel, :statements, :finallyBlock
      ]

      NODE_FIELDS = NESTABLE_NODE_FIELDS + UNNESTABLE_NODE_FIELDS

      attr_accessor *(NODE_FIELDS + NODE_METADATA_FIELDS)
      attr_accessor :capture

    	def initialize (t, type = nil)
    		token = t.token
    		if token
    			if type != nil
    				@type = type
    			else
    				@type = token.type
    			end
    			@value = token.value
    			@lineno = token.lineno
    			@start = token.start
    			@end = token.end
    	    @capture = token.capture
    		else
    			@type = type
    			@lineno = t.lineno
    		end
    		@tokenizer = t
    		#for (var i = 2; i < arguments.length; i++)
    		#this.push(arguments[i]);
    	end

      def node_type
        TOKENS[type]
      end

      # Hash representation of a single node
      # Construction does not descend child structures, (ie Node::NESTABLE_NODE_FIELDS, :contains)
      def to_searchable_hash
        r = SearchableHash.new :node_type => self.node_type
        Node::UNNESTABLE_NODE_FIELDS.each do |nf|
          v = self.send(nf)
          r[nf] = v if (v != nil || node_type == 'null') && (!v.respond_to?(:empty?) || !v.empty?)
        end
        r.capture = self.capture
        r
      end

      def to_tree
        r = self.to_searchable_hash
        Node::NESTABLE_NODE_FIELDS.each do |nf|
          t = self.send(nf)
          v = t.respond_to?(:to_tree) ? t.send(:to_tree) : nil
          r[nf] = v if v
        end

        custom_fields = {
          :contains => SearchableArray.new(*self.map do |child|
            child.send(:to_tree)
          end)
        }
        custom_fields.each do |k, v|
          r[k] = v if v && !v.empty?
        end

        return r
      end

    	# Always use push to add operands to an expression, to update start and end.
    	def push_with_end_tracking (kid)
    		if kid and kid.start and @start
    			@start = kid.start if kid.start < @start
    		end
    		if kid and kid.end and @end
    			@end = kid.end if @end < kid.end
    		end
    		return push_without_end_tracking(kid)
    	end
    	alias_method_chain :push, :end_tracking

    # 	def to_s
    # 		a = []
    # 		
    # 		#for (var i in this) {
    # 		#	if (this.hasOwnProperty(i) && i != 'type')
    # 		#		a.push({id: i, value: this[i]});
    # 		#}
    # 		#a.sort(function (a,b) { return (a.id < b.id) ? -1 : 1; });
    # 		iNDENTATION = "    "
    # 		n = (Node.indentLevel += 1)
    # 		t = TOKENS[@type]
    # 		s = "{\n" + iNDENTATION.repeat(n) +
    # 				"type: " + (/^\W/.test(t) and opTypeNames[t] or t.upcase)
    # 		#for (i = 0; i < a.length; i++)
    # 		#	s += ",\n" + INDENTATION.repeat(n) + a[i].id + ": " + a[i].value
    # 			s += ",\n" + iNDENTATION.repeat(n) + @value + ": " + a[i].value
    # 		n = (Node.indentLevel -= 1)
    # 		s += "\n" + iNDENTATION.repeat(n) + "}"
    # 		return s
    # 	end

    	def to_s
	
    		attrs = [@value,
    			@lineno, @start, @end,
    			@name, @params, @funDecls, @varDecls, @body, @functionForm,
    			@assignOp, @expression, @condition, @thenPart, @elsePart]
		
    		#puts TOKENS[@condition.type] if @condition != nil
		
    		#if /\A[a-z]/ =~ TOKENS[@type] # identifier
    		#	print @tokenizer.source.slice($cursor, @start - $cursor) if $cursor < @start
    		#	print '<span class="identifier">'
    		#	print @tokenizer.source.slice(@start, TOKENS[@type].length)
    		#	print '</span>'
    		#	$cursor = @start + TOKENS[@type].length
    		#end
		
    		#puts (" " * $ind) + "{" + TOKENS[@type] + "\n" if /\A[a-z]/ =~ TOKENS[@type]
    		#puts (" " * $ind) + " " + @start.to_s + "-" + @end.to_s + "\n"
    		$ind += 1
    		#puts @value
    		self.length.times do |i|
    			self[i].to_s if self[i] != self and self[i].class == Node
    		end
    		attrs.length.times do |attr|
    			if TOKENS[@type] == "if"
    			#	puts TOKENS[attrs[attr].type] if attrs[attr].class == Node and attrs[attr] !== self
    			end
    			attrs[attr].to_s if attrs[attr].class == Node #and attrs[attr] != self
    			#puts (" " * $ind).to_s + attrs[attr].to_s if attrs[attr].to_s != nil and attrs[attr] != self
    		end
    		$ind -= 1
    		#puts "\n}\n"

    		if $ind == 0
    			result = @tokenizer.source.slice($cursor, @tokenizer.source.length - $cursor)
    		end
		
    		return result
    	end

    	def getSource
    		return @tokenizer.source.slice(@start, @end)
    	end

    	def filename
    		return @tokenizer.filename
    	end

      def conditional?
        [ 'if', 'else', 'case' ].include?(TOKENS[@type])
      end
    end

    $cursor = 0

    $ind = 0

    def Script (t, x)
    	n = Statements(t, x)
    	n.type = $consts["SCRIPT"]
    	n.funDecls = x.funDecls
    	n.varDecls = x.varDecls
    	return n
    end


    # Statement stack and nested statement handler.
    # nb. Narcissus allowed a function reference, here we use Statement explicitly
    def nest (t, x, node, end_ = nil)
    	x.stmtStack.push(node)
    	n = Statement(t, x)
    	x.stmtStack.pop
    	end_ and t.mustMatch(end_)
    	return n
    end


    def Statements (t, x)
    	n = Node.new(t, $consts["BLOCK"])
    	x.stmtStack.push(n)
    	n.push(Statement(t, x)) while !t.done and t.peek != $consts["RIGHT_CURLY"]
    	x.stmtStack.pop
    	return n
    end


    def Block (t, x)
    	t.mustMatch($consts["LEFT_CURLY"])
    	n = Statements(t, x)
    	t.mustMatch($consts["RIGHT_CURLY"])
    	return n
    end


    DECLARED_FORM = 0
    EXPRESSED_FORM = 1
    STATEMENT_FORM = 2

    def Statement (t, x)
    	tt = t.get

    	# Cases for statements ending in a right curly return early, avoiding the
    	# common semicolon insertion magic after this switch.
    	case tt
    		when $consts["FUNCTION"]
    			return FunctionDefinition(t, x, true, 
    				(x.stmtStack.length > 1) && STATEMENT_FORM || DECLARED_FORM)

    		when $consts["LEFT_CURLY"]
    			n = Statements(t, x)
    			t.mustMatch($consts["RIGHT_CURLY"])
    			return n

    		when $consts["IF"]
    			n = Node.new(t)
    			n.condition = ParenExpression(t, x)
    			x.stmtStack.push(n)
    			n.thenPart = Statement(t, x)
    			n.elsePart = t.match($consts["ELSE"]) ? Statement(t, x) : nil
    			x.stmtStack.pop()
    			return n

    		when $consts["SWITCH"]
    			n = Node.new(t)
    			t.mustMatch($consts["LEFT_PAREN"])
    			n.discriminant = Expression(t, x)
    			t.mustMatch($consts["RIGHT_PAREN"])
    			n.cases = []
    			n.defaultIndex = -1
    			x.stmtStack.push(n)
    			t.mustMatch($consts["LEFT_CURLY"])
    			while (tt = t.get) != $consts["RIGHT_CURLY"]
    				case tt
    					when $consts["DEFAULT"], $consts["CASE"]
    						if tt == $consts["DEFAULT"] and n.defaultIndex >= 0
    							raise SyntaxError, JavascriptParser::format_error_message("More than one switch default", t)
    						end
    						n2 = Node.new(t)
    						if tt == $consts["DEFAULT"]
    							n.defaultIndex = n.cases.length
    						else
    							n2.caseLabel = Expression(t, x, $consts["COLON"])
    						end
					
    					else
    						raise SyntaxError, JavascriptParser::format_error_message("Invalid switch case", t)
    				end
    				t.mustMatch($consts["COLON"])
    				n2.statements = Node.new(t, $consts["BLOCK"])
    				while (tt = t.peek) != $consts["CASE"] and tt != $consts["DEFAULT"] and tt != $consts["RIGHT_CURLY"]
    					n2.statements.push(Statement(t, x))
    				end
    				n.cases.push(n2)
    			end
    			x.stmtStack.pop
    			return n
		
    		when $consts["FOR"]
    			n = Node.new(t)
    			n.isLoop = true
    			t.mustMatch($consts["LEFT_PAREN"])
    			if (tt = t.peek) != $consts["SEMICOLON"]
    				x.inForLoopInit = true
    				if tt == $consts["VAR"] or tt == $consts["CONST"]
    					t.get
    					n2 = Variables(t, x)
    				else
    					n2 = Expression(t, x)
    				end
    				x.inForLoopInit = false
    			end
    			if n2 and t.match($consts["IN"])
    				n.type = $consts["FOR_IN"]
    				if n2.type == $consts["VAR"]
    					if n2.length != 1
    						raise SyntaxError, JavascriptParser::format_error_message("Invalid for..in left-hand side", t)
    					end
    					# NB: n2[0].type == IDENTIFIER and n2[0].value == n2[0].name.
    					n.iterator = n2[0]
    					n.varDecl = n2
    				else
    					n.iterator = n2
    					n.varDecl = nil
    				end
    				n.object = Expression(t, x)
    			else
    				n.setup = n2 or nil
    				t.mustMatch($consts["SEMICOLON"])
    				n.condition = (t.peek == $consts["SEMICOLON"]) ? nil : Expression(t, x)
    				t.mustMatch($consts["SEMICOLON"])
    				n.update = (t.peek == $consts["RIGHT_PAREN"]) ? nil : Expression(t, x)
    			end
    			t.mustMatch($consts["RIGHT_PAREN"])
    			n.body = nest(t, x, n)
    			return n
		
    		when $consts["WHILE"]
    			n = Node.new(t)
    			n.isLoop = true
    			n.condition = ParenExpression(t, x)
    			n.body = nest(t, x, n)
    			return n
		
    		when $consts["DO"]
    			n = Node.new(t)
    			n.isLoop = true
    			n.body = nest(t, x, n, $consts["WHILE"])
    			n.condition = ParenExpression(t, x)
    			if !x.ecmaStrictMode
    				# <script language="JavaScript"> (without version hints) may need
    				# automatic semicolon insertion without a newline after do-while.
    				# See http://bugzilla.mozilla.org/show_bug.cgi?id=238945.
    				t.match($consts["SEMICOLON"])
    				return n
    			end
		
    		when $consts["BREAK"], $consts["CONTINUE"]
    			n = Node.new(t)
    			if t.peekOnSameLine == $consts["IDENTIFIER"]
    				t.get
    				n.label = t.token.value
    			end
    			ss = x.stmtStack
    			i = ss.length
    			label = n.label
    			if label
    				begin
    					i -= 1
    					raise SyntaxError, JavascriptParser::format_error_message("Label not found", t) if i < 0
    				end while (ss[i].label != label)
    			else
    				begin
    					i -= 1
    					raise SyntaxError, JavascriptParser::format_error_message("Invalid " + ((tt == $consts["BREAK"]) and "break" or "continue"), t) if i < 0
    				end while !ss[i].isLoop and (tt != $consts["BREAK"] or ss[i].type != $consts["SWITCH"])
    			end
    			n.target = ss[i]
		
    		when $consts["TRY"]
    			n = Node.new(t)
    			n.tryBlock = Block(t, x)
    			n.catchClauses = []
    			while t.match($consts["CATCH"])
    				n2 = Node.new(t)
    				t.mustMatch($consts["LEFT_PAREN"])
    				n2.varName = t.mustMatch($consts["IDENTIFIER"]).value
    				if t.match($consts["IF"])
    					raise SyntaxError, JavascriptParser::format_error_message("Illegal catch guard", t) if x.ecmaStrictMode
    					if n.catchClauses.length and !n.catchClauses.last.guard
    						raise SyntaxError, JavascriptParser::format_error_message("Guarded catch after unguarded", t)
    					end
    					n2.guard = Expression(t, x)
    				else
    					n2.guard = nil
    				end
    				t.mustMatch($consts["RIGHT_PAREN"])
    				n2.block = Block(t, x)
    				n.catchClauses.push(n2)
    			end
    			n.finallyBlock = Block(t, x) if t.match($consts["FINALLY"])
    			if !n.catchClauses.length and !n.finallyBlock
    				raise SyntaxError, JavascriptParser::format_error_message("Invalid try statement", t)
    			end
    			return n
		
    		when $consts["CATCH"]
    		when $consts["FINALLY"]
    			raise SyntaxError, JavascriptParser::format_error_message(TOKENS[tt] + " without preceding try", t)
		
    		when $consts["THROW"]
    			n = Node.new(t)
    			n.exception = Expression(t, x)
		
    		when $consts["RETURN"]
    			raise SyntaxError, JavascriptParser::format_error_message("Invalid return", t) unless x.inFunction
    			n = Node.new(t)
    			tt = t.peekOnSameLine
    			if tt != $consts["END"] and tt != $consts["NEWLINE"] and tt != $consts["SEMICOLON"] and tt != $consts["RIGHT_CURLY"]
    				n.value = Expression(t, x)
    			end
		
    		when $consts["WITH"]
    			n = Node.new(t)
    			n.object = ParenExpression(t, x)
    			n.body = nest(t, x, n)
    			return n
		
    		when $consts["VAR"], $consts["CONST"]
    			n = Variables(t, x)
		
    		when $consts["DEBUGGER"]
    			n = Node.new(t)
	
    		when $consts["NEWLINE"], $consts["SEMICOLON"]
    			n = Node.new(t, $consts["SEMICOLON"])
    			n.expression = nil
    			return n

    		else
    			if tt == $consts["IDENTIFIER"] and t.peek == $consts["COLON"]
    				label = t.token.value
    				ss = x.stmtStack
    				(ss.length - 1).times do |i|
    					raise SyntaxError, JavascriptParser::format_error_message("Duplicate label", t) if ss[i].label == label
    				end
    				t.get
    				n = Node.new(t, $consts["LABEL"])
    				n.label = label
    				n.statement = nest(t, x, n)
    				return n
    			end

    			t.unget
    			n = Node.new(t, $consts["SEMICOLON"])
    			n.expression = Expression(t, x)
    			n.end = n.expression.end
    	end

    	if t.lineno == t.token.lineno
    		tt = t.peekOnSameLine
    		if tt != $consts["END"] and tt != $consts["NEWLINE"] and tt != $consts["SEMICOLON"] and tt != $consts["RIGHT_CURLY"]
    			raise SyntaxError, JavascriptParser::format_error_message("Missing ; before statement", t)
    		end
    	end
    	t.match($consts["SEMICOLON"])
    	return n
    end


    def FunctionDefinition (t, x, requireName, functionForm)
    	f = Node.new(t)
    	if f.type != $consts["FUNCTION"]
    		f.type = (f.value == "get") and $consts["GETTER"] or $consts["SETTER"]
    	end
    	if t.match($consts["IDENTIFIER"])
    		f.name = t.token.value
    	elsif requireName
    		raise SyntaxError, JavascriptParser::format_error_message("Missing function identifier", t)
    	end
    	t.mustMatch($consts["LEFT_PAREN"])
    	f.params = []
    	while (tt = t.get) != $consts["RIGHT_PAREN"]
    		raise SyntaxError, JavascriptParser::format_error_message("Missing formal parameter", t) unless tt == $consts["IDENTIFIER"]
    		f.params.push(t.token.value)
    		t.mustMatch($consts["COMMA"]) unless t.peek == $consts["RIGHT_PAREN"]
    	end
	
    	t.mustMatch($consts["LEFT_CURLY"])
    	x2 = CompilerContext.new(true)
    	f.body = Script(t, x2)
    	t.mustMatch($consts["RIGHT_CURLY"])
    	f.end = t.token.end
    	f.functionForm = functionForm
    	x.funDecls.push(f) if functionForm == $consts["DECLARED_FORM"]
    	return f
    end


    def Variables (t, x)
    	n = Node.new(t)

    	begin
    		t.mustMatch($consts["IDENTIFIER"])
    		n2 = Node.new(t)
    		n2.name = n2.value
    		if t.match($consts["ASSIGN"])
    			raise SyntaxError, JavascriptParser::format_error_message("Invalid variable initialization", t) if t.token.assignOp
    			n2.initializer = Expression(t, x, $consts["COMMA"])
    		end
    		n2.readOnly = (n.type == $consts["CONST"])
    		n.push(n2)
    		x.varDecls.push(n2)
    	end while t.match($consts["COMMA"])
    	return n
    end


    def ParenExpression (t, x)
    	t.mustMatch($consts["LEFT_PAREN"])
    	n = Expression(t, x)
    	t.mustMatch($consts["RIGHT_PAREN"])
    	return n
    end


    def Expression(t, x, stop = nil)
    	operators = []
    	operands = []
    	bl = x.bracketLevel
    	cl = x.curlyLevel
    	pl = x.parenLevel
    	hl = x.hookLevel
	
    	def reduce(operators, operands, t)
    		n = operators.pop
    		op = n.type
    		arity = $opArity[op]
    		if arity == -2
    			if operands.length >= 2
    				# Flatten left-associative trees.
    				left = operands[operands.length - 2]
				
    				if left.type == op
    					right = operands.pop
    					left.push(right)
    					return left
    				end
    			end
    			arity = 2
    		end
		
    		# Always use push to add operands to n, to update start and end.
    		a = operands.slice!(operands.length - arity, operands.length)

    		arity.times do |i|
    			n.push(a[i])
    		end
		
    		# Include closing bracket or postfix operator in [start,end).
    		n.end = t.token.end if n.end < t.token.end
		
    		operands.push(n)
    		return n
    	end

    gotoloopContinue = false
    until gotoloopContinue or (t.token and t.token.type == $consts["END"])
    gotoloopContinue = catch(:gotoloop) do
    #loop:
    	while (tt = t.get) != $consts["END"]
    		# Stop only if tt matches the optional stop parameter, and that
    		# token is not quoted by some kind of bracket.
    		if tt == stop and x.bracketLevel == bl and x.curlyLevel == cl and x.parenLevel == pl and x.hookLevel == hl
    			throw :gotoloop, true
    		end
		
    		case tt
    			when $consts["SEMICOLON"]
    				# NB: cannot be empty, Statement handled that.
    				throw :gotoloop, true;
			
    			when $consts["ASSIGN"], $consts["HOOK"], $consts["COLON"]
    				if t.scanOperand
    					throw :gotoloop, true
    				end
								
    				# Use >, not >=, for right-associative ASSIGN and HOOK/COLON.
    				while operators.length > 0 && $opPrecedence[operators.last.type] && $opPrecedence[operators.last.type] > $opPrecedence[tt]
    					reduce(operators, operands, t)
    				end
    				if tt == $consts["COLON"]
    					n = operators.last
    					raise SyntaxError, JavascriptParser::format_error_message("Invalid label", t) if n.type != $consts["HOOK"]
    					n.type = $consts["CONDITIONAL"]
    					x.hookLevel -= 1
    				else
    					operators.push(Node.new(t))
    					if tt == $consts["ASSIGN"]
    						operands.last.assignOp = t.token.assignOp
    					else
    						x.hookLevel += 1 # tt == HOOK
    					end
    				end
    				t.scanOperand = true
			
    			when $consts["COMMA"],
    				# Treat comma as left-associative so reduce can fold left-heavy
    				# COMMA trees into a single array.
    				$consts["OR"], $consts["AND"], $consts["BITWISE_OR"], $consts["BITWISE_XOR"],
    				$consts["BITWISE_AND"], $consts["EQ"], $consts["NE"], $consts["STRICT_EQ"],
    				$consts["STRICT_NE"], $consts["LT"], $consts["LE"], $consts["GE"],
    				$consts["GT"], $consts["INSTANCEOF"], $consts["LSH"], $consts["RSH"],
    				$consts["URSH"], $consts["PLUS"], $consts["MINUS"], $consts["MUL"],
    				$consts["DIV"], $consts["MOD"], $consts["DOT"], $consts["IN"]

    				# An in operator should not be parsed if we're parsing the head of
    				# a for (...) loop, unless it is in the then part of a conditional
    				# expression, or parenthesized somehow.
    				if tt == $consts["IN"] and x.inForLoopInit and x.hookLevel == 0 and x.bracketLevel == 0 and x.curlyLevel == 0 and x.parenLevel == 0
    					throw :gotoloop, true
    				end
				
    				if t.scanOperand
    					throw :gotoloop, true
    				end

    				reduce(operators, operands, t) while operators.length > 0 && $opPrecedence[operators.last.type] && $opPrecedence[operators.last.type] >= $opPrecedence[tt]

    				if tt == $consts["DOT"]
    					t.mustMatch($consts["IDENTIFIER"])
    					node = Node.new(t, $consts["DOT"])
    					node.push(operands.pop)
    					node.push(Node.new(t))
    					operands.push(node)
    				else
    					operators.push(Node.new(t))
    					t.scanOperand = true
    				end
			
    			when $consts["DELETE"], $consts["VOID"], $consts["TYPEOF"], $consts["NOT"],
    				$consts["BITWISE_NOT"], $consts["UNARY_PLUS"], $consts["UNARY_MINUS"],
    				$consts["NEW"]

    				if !t.scanOperand
    					throw :gotoloop, true
    				end
    				operators.push(Node.new(t))
			
    			when $consts["INCREMENT"], $consts["DECREMENT"]
    				if t.scanOperand
    					operators.push(Node.new(t)) # prefix increment or decrement
    				else
    					# Use >, not >=, so postfix has higher precedence than prefix.
    					reduce(operators, operands, t) while operators.length > 0 && $opPrecedence[operators.last.type] && $opPrecedence[operators.last.type] > $opPrecedence[tt]
    					n = Node.new(t, tt)
    					n.push(operands.pop)
    					n.postfix = true
    					operands.push(n)
    				end
			
    			when $consts["FUNCTION"]
    				if !t.scanOperand
    					throw :gotoloop, true
    				end
    				operands.push(FunctionDefinition(t, x, false, $consts["EXPRESSED_FORM"]))
    				t.scanOperand = false
			
    			when $consts["NULL"], $consts["THIS"], $consts["TRUE"], $consts["FALSE"],
    				$consts["IDENTIFIER"], $consts["NUMBER"], $consts["STRING"],
    				$consts["REGEXP"]

    				if !t.scanOperand
    					throw :gotoloop, true
    				end
    				operands.push(Node.new(t))
    				t.scanOperand = false
			
    			when $consts["LEFT_BRACKET"]
    				if t.scanOperand
    					# Array initialiser.  Parse using recursive descent, as the
    					# sub-grammar here is not an operator grammar.
    					n = Node.new(t, $consts["ARRAY_INIT"])
    					while (tt = t.peek) != $consts["RIGHT_BRACKET"]
    						if tt == $consts["COMMA"]
    							t.get
    							n.push(nil)
    							next
    						end
    						n.push(Expression(t, x, $consts["COMMA"]))
    						break if !t.match($consts["COMMA"])
    					end
    					t.mustMatch($consts["RIGHT_BRACKET"])
    					operands.push(n)
    					t.scanOperand = false
    				else
    					# Property indexing operator.
    					operators.push(Node.new(t, $consts["INDEX"]))
    					t.scanOperand = true
    					x.bracketLevel += 1
    				end
			
    			when $consts["RIGHT_BRACKET"]
    				if t.scanOperand or x.bracketLevel == bl
    					throw :gotoloop, true
    				end
    				while reduce(operators, operands, t).type != $consts["INDEX"]
    					nil
    				end
    				x.bracketLevel -= 1
			
    			when $consts["LEFT_CURLY"]
    				if !t.scanOperand
    					throw :gotoloop, true
    				end
    				# Object initialiser.  As for array initialisers (see above),
    				# parse using recursive descent.
    				x.curlyLevel += 1
    				n = Node.new(t, $consts["OBJECT_INIT"])

    catch(:gotoobject_init) do
    #object_init:
    				if !t.match($consts["RIGHT_CURLY"])
    					begin
    						tt = t.get
    						if (t.token.value == "get" or t.token.value == "set") and t.peek == $consts["IDENTIFIER"]
    							raise SyntaxError, JavascriptParser::format_error_message("Illegal property accessor", t) if x.ecmaStrictMode
    							n.push(FunctionDefinition(t, x, true, $consts["EXPRESSED_FORM"]))
    						else
    							case tt
    								when $consts["IDENTIFIER"], $consts["NUMBER"], $consts["STRING"]
    									id = Node.new(t)
								
    								when $consts["RIGHT_CURLY"]
    									raise SyntaxError, JavascriptParser::format_error_message("Illegal trailing ,", t) if x.ecmaStrictMode
    									throw :gotoobject_init
								
    								else
    									raise SyntaxError, JavascriptParser::format_error_message("Invalid property name", t)
    							end
    							t.mustMatch($consts["COLON"])
    							n2 = Node.new(t, $consts["PROPERTY_INIT"])
    							n2.push(id)
    							n2.push(Expression(t, x, $consts["COMMA"]))
    							n.push(n2)
    						end
    					end while t.match($consts["COMMA"])
    					t.mustMatch($consts["RIGHT_CURLY"])
    				end
    				operands.push(n)
    				t.scanOperand = false
    				x.curlyLevel -= 1
    end

    			when $consts["RIGHT_CURLY"]
    				raise SyntaxError, JavascriptParser::format_error_message("PANIC: right curly botch", t) if !t.scanOperand and x.curlyLevel != cl
    				throw :gotoloop, true
			
    			when $consts["LEFT_PAREN"]
    				if t.scanOperand
    					operators.push(Node.new(t, $consts["GROUP"]))
    				else
    					reduce(operators, operands, t) while operators.length > 0 && $opPrecedence[operators.last.type] && $opPrecedence[operators.last.type] > $opPrecedence[$consts["NEW"]]
    					# Handle () now, to regularize the n-ary case for n > 0.
    					# We must set scanOperand in case there are arguments and
    					# the first one is a regexp or unary+/-.
    					n = operators.last
    					t.scanOperand = true
    					if t.match($consts["RIGHT_PAREN"])
    						if n && n.type == $consts["NEW"]
    							operators.pop
    							n.push(operands.pop)
    						else
    							n = Node.new(t, $consts["CALL"])
    							n.push(operands.pop)
    							n.push(Node.new(t, $consts["LIST"]))
    						end
    						operands.push(n)
    						t.scanOperand = false
    						#puts "woah"
    						break
    					end
    					if n && n.type == $consts["NEW"]
    						n.type = $consts["NEW_WITH_ARGS"]
    					else
    						operators.push(Node.new(t, $consts["CALL"]))
    					end
    				end
    				x.parenLevel += 1
				
    			when $consts["RIGHT_PAREN"]
    				if t.scanOperand or x.parenLevel == pl
    					throw :gotoloop, true
    				end
    				while (tt = reduce(operators, operands, t).type) != $consts["GROUP"] \
    						and tt != $consts["CALL"] and tt != $consts["NEW_WITH_ARGS"]
    					nil
    				end
    				if tt != $consts["GROUP"]
    					n = operands.last
    					if n[1].type != $consts["COMMA"]
    						n2 = n[1]
    						n[1] = Node.new(t, $consts["LIST"])
    						n[1].push(n2)
    					else
    						n[1].type = $consts["LIST"]
    					end
    				end
    				x.parenLevel -= 1

    			# Automatic semicolon insertion means we may scan across a newline
    			# and into the beginning of another statement.  If so, break out of
    			# the while loop and let the t.scanOperand logic handle errors.
    			else
    				throw :gotoloop, true
    		end
    	end

    end
    end

    	raise SyntaxError, JavascriptParser::format_error_message('Missing : after ?', t) if x.hookLevel != hl
    	raise SyntaxError, JavascriptParser::format_error_message('Missing operand', t) if t.scanOperand
		
    	# Resume default mode, scanning for operands, not operators.
    	t.scanOperand = true
    	t.unget
    	reduce(operators, operands, t) while operators.length > 0
    	return operands.pop
    end

    def self.format_error_message msg, tokenizer
      # "#{msg} on line #{tokenizer.lineno} at #{TOKENS[tokenizer.token.type]}#{tokenizer.input}"
      "#{msg} on line #{tokenizer.lineno}"
    end

    def parse (source, filename = '', line = 1)
    	t = Tokenizer.new(source, filename, line)
    	t.parse_substitutes = true
    	x = CompilerContext.new(false)
    	n = Script(t, x)
    	raise SyntaxError, JavascriptParser::format_error_message("Syntax error", t) if !t.done
        return n
    end

  end

end
